#leetcode题目56：合并区间
#难度：中等
#时间复杂度：O(nlogn)
#空间复杂度：O(1)
#方法：排序

from typing import List
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort()
        res=[intervals[0]]
        for x,y in intervals[1:]:
            if x>res[-1][1]:
                res.append([x,y])
            else:
                y=max(res[-1][1],y)
                res[-1][1]=y
        return res


#测试数据
intervals=[[1,3],[2,6],[8,10],[15,18]]
#预期输出：[[1,6],[8,10],[15,18]]
solution=Solution()
print(solution.merge(intervals))

intervals=[[1,4],[4,5]]
#预期输出：[[1,5]]
solution=Solution()
print(solution.merge(intervals))

